Types of wireless networks include infrastructure-based wireless networks and ad hoc wireless networks.
Ad hoc networks are self-forming networks which can operate in the absence of any fixed infrastructure, and in some cases the ad hoc network is formed entirely of mobile nodes. An ad hoc network typically includes a number of geographically-distributed, potentially mobile units, sometimes referred to as “nodes,” which are wirelessly connected to each other by one or more links (e.g., radio frequency communication channels). The nodes can communicate with each other over a wireless media without the support of an infrastructure-based or wired network. Links or connections between these nodes can change dynamically in an arbitrary manner as existing nodes move within the ad hoc network, as new nodes join or enter the ad hoc network, or as existing nodes leave or exit the ad hoc network. Because the topology of an ad hoc network can change significantly techniques are needed which can allow the ad hoc network to dynamically adjust to these changes. Due to the lack of a central controller, many network-controlling functions can be distributed among the nodes such that the nodes can self-organize and reconfigure in response to topology changes.
One characteristic of ad hoc network nodes is that each node can directly communicate over a short range with nodes which are a single “hop” away. Such nodes are sometimes referred to as “neighbor nodes.” When a node transmits packets to a destination node and the nodes are separated by more than one hop (e.g., the distance between two nodes exceeds the radio transmission range of the nodes, or a physical barrier is present between the nodes), the packets can be relayed via intermediate nodes (“multi-hopping”) until the packets reach the destination node. In such situations, each intermediate node routes the packets (e.g., data and control information) to the next node along the route, until the packets reach their final destination. For relaying packets to the next node, each node maintains routing information collected through conversation with its neighboring nodes. The routing information can also be periodically broadcast in the network to reflect the current network topology. Alternatively, to reduce the amount of information transmitted for maintaining accurate routing information, the network nodes may exchange routing information only when it is needed. One approach for routing information, known as Mesh Scalable Routing (MSR), is described in United States Patent Application Publication Number 20040143842 entitled “System And Method For Achieving Continuous Connectivity To An Access Point Or Gateway In A Wireless Network Following An On-Demand Routing Protocol, And To Perform Smooth Handoff Of Mobile Terminals Between Fixed Terminals In The Network,” filed Jan. 13, 2004, which is incorporated by reference herein in its entirety.
Time Division Multiple Access (TDMA) is a shared medium access technology that is commonly used in digital cellular networks, satellite networks, local area networks, and other shared medium networks. In TDMA-based systems, a radio frequency is divided into time slots, and a unit may transmit in one or several time slots which are assigned to that unit. The users transmit in rapid succession, one after the other, each using their assigned timeslot(s). This allows multiple users to share the same transmission medium (e.g., radio frequency) while using only the part of its bandwidth which they require.
Most TDMA systems use centralized time slot allocation. For example, in a cellular system, a base station is the central authority which controls time slot allocation. In a local area network (LAN), an access point is the central node which controls time slot allocation. TDMA medium access control (MAC) protocols allow several users to share the same frequency by dividing it into different timeslots. TDMA MAC protocols require time synchronization and slot reservation for collision free transmission. TDMA MAC protocols are generally regarded as being efficient for periodic, delay sensitive traffic (e.g., voice traffic and video traffic), since they provide contention free transmission.
Centralized allocation of timeslots requires exchanging a large amount of network management information, which consumes valuable communication bandwidth. Centralized timeslot allocation techniques are typically applied in networks where the length of the communication path is relatively small (e.g., only one hop). Applying centralized timeslot allocation techniques in multi-hopping networks can be problematic because the of the significant amount of time required for propagating information from nodes at the periphery of the network to a central node, and for propagating information from the central node back to the nodes at the periphery of the network. Centralized timeslot allocation techniques can be inefficient for reaching all network nodes due to mobility of nodes and the relatively long time needed for propagating the information to each node in the network. For this reason, in mobile multi-hopping networks, where the topology of nodes changes frequently, the utilization of centralized timeslot allocation techniques can be prohibitive.
In many multi-hop ad hoc networks, including those which use a Time Division Multiple Access (TDMA) Media Access Control (MAC) protocols, multiple routes can be present between a source node and a destination node for communication of a particular data stream. In some communication scenarios some or even all of the routes may not support Quality-of-Service (QoS) requirements of the particular data stream. This can occur, for example, when certain routes do not have a sufficient number of time slots to sustain the particular data stream.
Skilled artisans will appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help to improve understanding of embodiments of the present invention.